package microsoft;

import java.util.Arrays;

/**
 * @author pengfei.hpf
 * @date 2020/2/25
 * @verdion 1.0.0
 * 电话面试, network
 */
public class quicksort {

    private int quicksort(int[] nums, int start, int end){
        int p = nums[start];
        swap(nums, start, end);
        int small = start -1;
        for(int i = start; i < end; i ++){
            if(nums[i]< p){
                small ++;
                if(i != small){
                    swap(nums, i, small);
                }
            }
        }
        swap(nums, small +1, end);
        return small + 1;
    }

    private void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    private void partion(int[] nums, int start, int end){
        if(start >= end){
            return;
        }
        int p = quicksort(nums, start, end);
        partion(nums, start, p - 1);
        partion(nums, p + 1, end);
    }

    public void sort(int[] nums){
        if(nums == null || nums.length <= 1){
            return;
        }

        partion(nums, 0, nums.length - 1);
    }

    public static void main(String[] args){
        int[] nums = new int[]{2,1,4,9,6,3,2};
        new quicksort().sort(nums);
        for(int i = 0; i < nums.length; i ++){
            System.out.print(nums[i] + " ");
        }
    }
}
